# my naive solution
class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        record = [False]*n
        def find(begin, sum):
            for i in range(begin, len(nums)):
                num = nums[i]
                sum += num
                if 0<=sum-1<n:
                    record[sum-1]=True
                    find(i+1, sum)
                sum -= num
        
        find(0, 0)
        patch = 0
        for i in range(1, n):
            if not record[i-1]:
                nums.append(i)
                patch += 1
                find(0, 0)
        return patch

print(Solution().minPatches([1,2,2], 5))
[1,2,31,33]
2147483647